AsInstrategic classification, aninstitution(e.g., a bank) anticipates adaptation from userswe develop better algorithms under varying assumpwho change their features to increase utilitytions about adaptation (Levanon and Rosenfeld, 2022; in a classification task (e.g., loan repayment). Kleinberg and Raghavan, 2018), there are growing Since a key challenge is the distribution shiftconcerns about negative social impact on the agents who adapt to these systems, whether outcomes areinduced by users, we turn to causal models, which have been shown to bound the worst-static (Milli et al., 2019) or dynamic (G ois et al., case out-of-distribution (OOD) risk, and es-2025). When agents adapt, depending on the untablish several new results that link causal-derlying causal model (Horowitz and Rosenfeld, 2018; ity and strategic classification. First, we Miller et al., 2020), some changes improve agent outcomes while others constitute gaming the classifier,show that causal classification leads to optimal classification error after any sufficientlyworsening classification error. In this paper, we study large adaptation, when the noise is boundedwhether classifiers can maintain accuracy without sacin a certain way. Second, when these as-rificing alignment with predicted agent's goals.

Machine Learning critically relies on the assumption that the training data is representative of the unseen instances a learner faces at test time.

However, in reality, this may not always be the case.

We begin by providing online mistake bounds and P AC sample complexity in these scenarios for ball manipulations.

We study the fundamental mistake bound and sample complexity in the strategic classification, where agents can strategically manipulate their feature vector up to an extent in order to be predicted as positive. For example, given a classifier determining college admission, student candidates may try to take easier classes to improve their GPA, retake SAT and change schools in an effort to fool the classifier.

We initiate the study of active learning algorithms for classifying strategic agents. Active learning is a well-established framework in machine learning in which the learner selectively queries labels, often achieving substantially higher accuracy and efficiency than classical supervised methods-especially in settings where labeling is costly or time-consuming, such as hiring, admissions, and loan decisions. Strategic classification, however, addresses scenarios where agents modify their features to obtain more favorable outcomes, resulting in observed data that is not truthful. Such manipulation introduces challenges beyond those in learning from clean data. Our goal is to design active and noise-tolerant algorithms that remain effective in strategic environments-algorithms that classify strategic agents accurately while issuing as few label requests as possible. The central difficulty is to simultaneously account for strategic manipulation and preserve the efficiency gains of active learning. Our main result is an algorithm for actively learning linear separators in the strategic setting that preserves the exponential improvement in label complexity over passive learning previously obtained only in the non-strategic case. Specifically, for data drawn uniformly from the unit sphere, we show that a modified version of the Active Perceptron algorithm [DKM05,YZ17] achieves excess error $ε$ using only $\tilde{O}(d \ln \frac{1}ε)$ label queries and incurs at most $\tilde{O}(d \ln \frac{1}ε)$ additional mistakes relative to the optimal classifier, even in the nonrealizable case, when a $\tildeΩ(ε)$ fraction of inputs have inconsistent labels with the optimal classifier. The algorithm is computationally efficient and, under these distributional assumptions, requires substantially fewer label queries than prior work on strategic Perceptron [ABBN21].